/*
 * @lc app=leetcode.cn id=84 lang=cpp
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int ans = 0;
        stack<int> s;
        heights.push_back(0);

        int i = 0;
        for (; i < heights.size(); i++)
        {
            if (s.size() == 0)
            {
                s.push(i);
            }
            else
            {
                int j = s.top();
                if (heights[i] == heights[j])
                {
                    s.push(i);
                }
                else if (heights[i] < heights[j])
                {
                    while (!s.empty() && heights[i] < heights[s.top()])
                    {
                        j = s.top();
                        s.pop();
                        if (s.size() == 0)
                        {
                            ans = max(ans, heights[j] * i);
                        }
                        else
                        {
                            ans = max(ans, heights[j] * (i- s.top() - 1));
                        }
                    }
                    s.push(i);
                }
                else
                {
                    s.push(i);
                }
            }
        }

        return ans;
    }
};
// int main()
// {
//     vector<int> nums = {1,0,0,1,0,1,0,0,0,1};
//     // vector<int> nums = {2,1,5,6,2,3};
//     // vector<int> nums = {4,2,0,3,2,5};


//     cout << Solution().largestRectangleArea(nums) << endl;
//     return 0;
// }
// @lc code=end
